Mutual Recursion on:
[Wikipedia]
[Google]
[Amazon]
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, mutual recursion is a form of
recursion
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
where two mathematical or computational objects, such as functions or datatypes, are defined in terms of each other. Mutual recursion is very common in
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
and in some problem domains, such as
recursive descent parser
In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus t ...
s, where the datatypes are naturally mutually recursive.
Examples
Datatypes
The most important basic example of a datatype that can be defined by mutual recursion is a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
, which can be defined mutually recursively in terms of a forest (a list of trees). Symbolically:
f:
[1_...,_t[k.html"_;"title=".html"_;"title="[1">[1_...,_t[k">.html"_;"title="[1">[1_...,_t[k
_t:_v_f
A_forest_''f''_consists_of_a_list_of_trees,_while_a_tree_''t''_consists_of_a_pair_of_a_value_''v''_and_a_forest_''f''_(its_children)._This_definition_is_elegant_and_easy_to_work_with_abstractly_(such_as_when_proving_theorems_about_properties_of_trees),_as_it_expresses_a_tree_in_simple_terms:_a_list_of_one_type,_and_a_pair_of_two_types._Further,_it_matches_many_algorithms_on_trees,_which_consist_of_doing_one_thing_with_the_value,_and_another_thing_with_the_children.
This_mutually_recursive_definition_can_be_converted_to_a_singly_recursive_definition_by_Inline_expansion.html" "title="">[1_...,_t[k.html" ;"title=".html" ;"title="[1">[1 ..., t[k">.html" ;"title="[1">[1 ..., t[k
t: v f
A forest ''f'' consists of a list of trees, while a tree ''t'' consists of a pair of a value ''v'' and a forest ''f'' (its children). This definition is elegant and easy to work with abstractly (such as when proving theorems about properties of trees), as it expresses a tree in simple terms: a list of one type, and a pair of two types. Further, it matches many algorithms on trees, which consist of doing one thing with the value, and another thing with the children.
This mutually recursive definition can be converted to a singly recursive definition by Inline expansion">inlining
In computing, inline expansion, or inlining, is a manual or compiler optimization that replaces a function call site with the body of the called function. Inline expansion is similar to macro expansion, but occurs during compilation, without cha ...
the definition of a forest:
t: v
[1_...,_t[k.html" ;"title=".html" ;"title="[1">[1 ..., t[k">.html" ;"title="[1">[1 ..., t[k
A tree ''t'' consists of a pair of a value ''v'' and a list of trees (its children). This definition is more compact, but somewhat messier: a tree consists of a pair of one type and a list of another, which require disentangling to prove results about.
In Standard ML, the tree and forest datatypes can be mutually recursively defined as follows, allowing empty trees:
datatype 'a tree = Empty , Node of 'a * 'a forest
and 'a forest = Nil , Cons of 'a tree * 'a forest
Computer functions
Just as algorithms on recursive datatypes can naturally be given by recursive functions, algorithms on mutually recursive data structures can be naturally given by mutually recursive functions. Common examples include algorithms on trees, and
recursive descent parser
In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus t ...
s. As with direct recursion,
tail call optimization
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
is necessary if the recursion depth is large or unbounded, such as using mutual recursion for multitasking. Note that tail call optimization in general (when the function called is not the same as the original function, as in tail-recursive calls) may be more difficult to implement than the special case of tail-recursive call optimization, and thus efficient implementation of mutual tail recursion may be absent from languages that only optimize tail-recursive calls. In languages such as
Pascal
Pascal, Pascal's or PASCAL may refer to:
People and fictional characters
* Pascal (given name), including a list of people with the name
* Pascal (surname), including a list of people and fictional characters with the name
** Blaise Pascal, Fren ...
that require declaration before use, mutually recursive functions require
forward declaration
In computer programming, a forward declaration is a declaration of an identifier (denoting an entity such as a type, a variable, a constant, or a function) for which the programmer has not yet given a complete definition.
It is required for a com ...
, as a forward reference cannot be avoided when defining them.
As with directly recursive functions, a
wrapper function
A wrapper function is a function (another word for a ''subroutine'') in a software library or a computer program whose main purpose is to call a second subroutine or a system call with little or no additional computation. Wrapper functions are us ...
may be useful, with the mutually recursive functions defined as
nested function
In computer programming, a nested function (or nested procedure or subroutine) is a function which is defined within another function, the ''enclosing function''. Due to simple recursive scope rules, a nested function is itself invisible outside o ...
s within its scope if this is supported. This is particularly useful for sharing state across a set of functions without having to pass parameters between them.
Basic examples
A standard example of mutual recursion, which is admittedly artificial, determines whether a non-negative number is even or odd by defining two separate functions that call each other, decrementing by 1 each time. In C:
bool is_even(unsigned int n)
bool is_odd(unsigned int n)
These functions are based on the observation that the question ''is 4 even?'' is equivalent to ''is 3 odd?'', which is in turn equivalent to ''is 2 even?'', and so on down to 0. This example is mutual
single recursion, and could easily be replaced by iteration. In this example, the mutually recursive calls are
tail call
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
s, and tail call optimization would be necessary to execute in constant stack space. In C, this would take ''O''(''n'') stack space, unless rewritten to use jumps instead of calls. This could be reduced to a single recursive function
is_even. In that case,
is_odd, which could be inlined, would call
is_even, but
is_even would only call itself.
As a more general class of examples, an algorithm on a tree can be decomposed into its behavior on a value and its behavior on children, and can be split up into two mutually recursive functions, one specifying the behavior on a tree, calling the forest function for the forest of children, and one specifying the behavior on a forest, calling the tree function for the tree in the forest. In Python:
def f_tree(tree) -> None:
f_value(tree.value)
f_forest(tree.children)
def f_forest(forest) -> None:
for tree in forest:
f_tree(tree)
In this case the tree function calls the forest function by single recursion, but the forest function calls the tree function by
multiple recursion
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves ...
.
Using the Standard ML datatype above, the size of a tree (number of nodes) can be computed via the following mutually recursive functions:
fun size_tree Empty = 0
, size_tree (Node (_, f)) = 1 + size_forest f
and size_forest Nil = 0
, size_forest (Cons (t, f')) = size_tree t + size_forest f'
A more detailed example in Scheme, counting the leaves of a tree:
(define (count-leaves tree)
(if (leaf? tree)
1
(count-leaves-in-forest (children tree))))
(define (count-leaves-in-forest forest)
(if (null? forest)
0
(+ (count-leaves (car forest))
(count-leaves-in-forest (cdr forest)))))
These examples reduce easily to a single recursive function by inlining the forest function in the tree function, which is commonly done in practice: directly recursive functions that operate on trees sequentially process the value of the node and recurse on the children within one function, rather than dividing these into two separate functions.
Advanced examples
A more complicated example is given by
recursive descent parser
In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus t ...
s, which can be naturally implemented by having one function for each
production rule of a grammar, which then mutually recurse; this will in general be multiple recursion, as production rules generally combine multiple parts. This can also be done without mutual recursion, for example by still having separate functions for each production rule, but having them called by a single controller function, or by putting all the grammar in a single function.
Mutual recursion can also implement a
finite-state machine
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
, with one function for each state, and single recursion in changing state; this requires tail call optimization if the number of state changes is large or unbounded. This can be used as a simple form of
cooperative multitasking
Cooperative multitasking, also known as non-preemptive multitasking, is a style of computer multitasking in which the operating system never initiates a context switch from a running process to another process. Instead, in order to run multiple ...
. A similar approach to multitasking is to instead use
coroutine
Coroutines are computer program components that generalize subroutines for non-preemptive multitasking, by allowing execution to be suspended and resumed. Coroutines are well-suited for implementing familiar program components such as cooperative ...
s which call each other, where rather than terminating by calling another routine, one coroutine yields to another but does not terminate, and then resumes execution when it is yielded back to. This allows individual coroutines to hold state, without it needing to be passed by parameters or stored in shared variables.
There are also some algorithms which naturally have two phases, such as
minimax
Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When de ...
(min and max), which can be implemented by having each phase in a separate function with mutual recursion, though they can also be combined into a single function with direct recursion.
Mathematical functions
In mathematics, the
Hofstadter Female and Male sequences In mathematics, a Hofstadter sequence is a member of a family of related integer sequences defined by non-linear recurrence relations.
Sequences presented in ''Gödel, Escher, Bach: an Eternal Golden Braid''
The first Hofstadter sequences were desc ...
are an example of a pair of integer sequences defined in a mutually recursive manner.
Fractals can be computed (up to a given resolution) by recursive functions. This can sometimes be done more elegantly via mutually recursive functions; the
Sierpiński curve
Sierpiński curves are a recursively defined sequence of continuous closed plane fractal curves discovered by Wacław Sierpiński, which in the limit n \to \infty completely fill the unit square: thus their limit curve, also called the Sierpiń ...
is a good example.
Prevalence
Mutual recursion is very common in
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
, and is often used for programs written in
LISP
A lisp is a speech impairment in which a person misarticulates sibilants (, , , , , , , ). These misarticulations often result in unclear speech.
Types
* A frontal lisp occurs when the tongue is placed anterior to the target. Interdental lisping ...
,
Scheme A scheme is a systematic plan for the implementation of a certain idea.
Scheme or schemer may refer to:
Arts and entertainment
* ''The Scheme'' (TV series), a BBC Scotland documentary series
* The Scheme (band), an English pop band
* ''The Schem ...
,
ML, and similar
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s. For example, Abelson and Sussman describe how a
meta-circular evaluator In computing, a meta-circular evaluator (MCE) or meta-circular interpreter (MCI) is an interpreter which defines each feature of the interpreted language using a similar facility of the interpreter's host language. For example, interpreting a lambd ...
can be used to implement LISP with an eval-apply cycle. In languages such as
Prolog
Prolog is a logic programming language associated with artificial intelligence and computational linguistics.
Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primarily ...
, mutual recursion is almost unavoidable.
Some programming styles discourage mutual recursion, claiming that it can be confusing to distinguish the conditions which will return an answer from the conditions that would allow the code to run forever without producing an answer.
Peter Norvig
Peter Norvig (born December 14, 1956) is an American computer scientist and Distinguished Education Fellow at the Stanford Institute for Human-Centered AI. He previously served as a director of research and search quality at Google. Norvig is t ...
points to a
design pattern
A design pattern is the re-usable form of a solution to a design problem. The idea was introduced by the architect Christopher Alexander and has been adapted for various other disciplines, particularly software engineering. The " Gang of Four" b ...
which discourages the use entirely, stating:
Terminology
Mutual recursion is also known as
indirect recursion, by contrast with
direct recursion, where a single function calls itself directly. This is simply a difference of emphasis, not a different notion: "indirect recursion" emphasises an individual function, while "mutual recursion" emphasises the set of functions, and does not single out an individual function. For example, if ''f'' calls itself, that is direct recursion. If instead ''f'' calls ''g'' and then ''g'' calls ''f,'' which in turn calls ''g'' again, from the point of view of ''f'' alone, ''f'' is indirectly recursing, while from the point of view of ''g'' alone, ''g'' is indirectly recursing, while from the point of view of both, ''f'' and ''g'' are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.
Conversion to direct recursion
Mathematically, a set of mutually recursive functions are
primitive recursive
In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
, which can be proven by
course-of-values recursion
In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n'') is computed from the sequence \lan ...
, building a single function ''F'' that lists the values of the individual recursive function in order:
and rewriting the mutual recursion as a primitive recursion.
Any mutual recursion between two procedures can be converted to direct recursion by inlining the code of one procedure into the other. If there is only one site where one procedure calls the other, this is straightforward, though if there are several it can involve code duplication. In terms of the call stack, two mutually recursive procedures yield a stack ABABAB..., and inlining B into A yields the direct recursion (AB)(AB)(AB)...
Alternately, any number of procedures can be merged into a single procedure that takes as argument a
variant record
In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type or coproduct, is a data structure used to hold a value that could take on several different, but fixed, types. O ...
(or
algebraic data type
In computer programming, especially functional programming and type theory, an algebraic data type (ADT) is a kind of composite type, i.e., a type formed by combining other types.
Two common classes of algebraic types are product types (i.e., t ...
) representing the selection of a procedure and its arguments; the merged procedure then dispatches on its argument to execute the corresponding code and uses direct recursion to call self as appropriate. This can be seen as a limited application of
defunctionalization
In programming languages, defunctionalization is a compile-time transformation which eliminates higher-order functions, replacing them by a single first-order ''apply'' function. The technique was first described by John C. Reynolds in his 1972 p ...
.
This translation may be useful when any of the mutually recursive procedures can be called by outside code, so there is no obvious case for inlining one procedure into the other. Such code then needs to be modified so that procedure calls are performed by bundling arguments into a variant record as described; alternately, wrapper procedures may be used for this task.
See also
*
Cycle detection (graph theory)
In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.
A graph witho ...
*
Recursion (computer science)
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves ...
*
Circular dependency
In software engineering, a circular dependency is a relation between two or more modules which either directly or indirectly depend on each other to function properly. Such modules are also known as mutually recursive.
Overview
Circular depend ...
References
*
*
* {{cite book , title=Programming in Haskell , last=Hutton , first=Graham , year=2007 , publisher=Cambridge University Press , isbn=978-0-52169269-4
External links
Mutual recursionat
Rosetta Code
Rosetta Code is a wiki-based programming website with implementations of common algorithms and solutions to various programming problems in many different programming languages. It is named for the Rosetta Stone, which has the same text inscribe ...
*
Example demonstrating good use of mutual recursion,
Are there any example of Mutual recursion?, ''Stack Overflow''
Theory of computation
Recursion